#pragma once
#include <vector>
#include<stdlib.h>
#include<iostream>

using namespace std;

template<typename T> 
vector<T> insertionSort(vector<T> & dataList)
{
	for (int index = 1; index < dataList.size(); index++)
	{
		T key = dataList.at(index);
		int iterator = index - 1;

		//Because in C++, index starts from 0, so iterator >= 0;
		while ((iterator >= 0) && (dataList.at(iterator) > key))
		{
			dataList.at(iterator + 1) = dataList.at(iterator);
			--iterator;
		}//end inner loop
		dataList.at(iterator + 1) = key;
	}//end loop

	return dataList;
};//end function